//和最小的 k 个数对
class Solution {
public:
    struct cmp
    {
        bool operator()(const pair<int,int>&p1, const pair<int,int>&p2)
        {
            return p1.first+p1.second>p2.first+p2.second;
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) 
    {
        vector<vector<int>>res;
        int m=nums1.size();
        int n=nums2.size();
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                q.push(make_pair(nums1[i],nums2[j]));
            }
        }
        k=min(k,(int)q.size());
        while(k--)
        {
            pair<int,int>cur=q.top();
            q.pop();
            res.push_back({cur.first,cur.second});
        }
        return res;
    }
};

//单词替换
struct TrieNode
{
    bool _isend;
    TrieNode* _next[26];
    TrieNode()
        :_isend(false)
    {
        memset(_next,0,sizeof(_next));
    }
};
class Trie
{
public:
    Trie()
    {
        _head=new TrieNode();
    }
    void insert(string word)
    {
        TrieNode* cur=_head;
        for(auto ch:word)
        {
            if(cur->_next[ch-'a']==nullptr)
            {
                cur->_next[ch-'a']=new TrieNode();
            }
            cur=cur->_next[ch-'a'];
        }
        cur->_isend=true;
    }
    string findfront(string word)
    {
        string tmp;
        TrieNode *cur=_head;
        for(auto ch:word)
        {
            tmp+=ch;
            //如果把dictionary全部录入后 找到了空
            //说明该单词没有已知的前缀
            if(cur->_next[ch-'a']==nullptr) return word;
            if(cur->_next[ch-'a']->_isend) return tmp;
            cur=cur->_next[ch-'a'];
        }
        return tmp;
    }
private:
    TrieNode* _head;
};
class Solution 
{
public:
    string replaceWords(vector<string>& dictionary, string sentence) 
    {
        Trie tree;
        for(auto str:dictionary)
        {
            tree.insert(str);
        }
        vector<string> v;
        string tmp;
        for(int i=0;i<=sentence.size();i++)
        {
            if(i==sentence.size())
            {
                v.push_back(tmp);
            }
            if(i<sentence.size() && sentence[i]==' ')
            {
                v.push_back(tmp);
                tmp.clear();
            }
            if(i<sentence.size() && sentence[i]!=' ')
            {
                tmp+=sentence[i];
            }
        }
        string res;
        for(int i=0;i<v.size();i++)
        {
            res+=tree.findfront(v[i]);
            if(i==v.size()-1) break;
            else res+=' ';
        }
        return res;
    }
};

//神奇的字典
struct Trie {
    bool isEnd = false;
    vector<Trie*> nexts;
    Trie() : nexts(26, nullptr) {}
};

class MagicDictionary {
private:
    Trie* trie = new Trie();
public:
    MagicDictionary() {}
    void buildDict(vector<string> dictionary) {
        // 构建字典树
        for (string &word : dictionary) 
        {
            Trie* curr = trie;
            for (char &ch : word)
            {
                ch -= 'a';
                if (curr->nexts[ch] == nullptr) 
                {
                    curr->nexts[ch] = new Trie();
                }
                curr = curr->nexts[ch];
            }
            curr->isEnd = true; // 标记单词结尾
        }
    }
    bool search(string searchWord) 
    {
        // 每查询一个单词我们都要检查一下每条分支
        return dfs(trie, searchWord, 0, 0);
    }
    bool dfs(Trie* curr, string& word, int idx, int craft) 
    {
        if (curr == nullptr) 
        { // 走到了字典树上没有的位置
            return false;
        }
        if (curr->isEnd && idx == word.size() && craft == 1) 
        { // 唯一正确出口
            return true;
        }

        if (idx< word.size() && craft <= 1) 
        {
            bool found = false;
            for (int j = 0; j < 26 && !found; j++) 
            {
                int _craft = (word[idx] - 'a' == j) ? craft : craft + 1; 
                found = dfs(curr->nexts[j], word, idx + 1, _craft);
            }
            return found;
        }
        return false;
    }
};